package datastructure.sort;

/**
 * @author yinlei
 * @date 2018/7/2
 * @since 1.0.0
 */
public class SelectionSort implements SortMain.Sort {

    public void sort(int[] a) {

        for (int i = 0; i < a.length; i++) {
            int min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            SortUtil.swap(a, i, min);
        }
    }

    private static void sort2(int[] a) {
        int n = a.length;
        for (int i = 0; i < n / 2; i++) {
            int max = i;
            int min = i;
            for (int j = i + 1; j < n - i; j++) {
                if (a[max] < a[j]) {
                    max = j;
                }
                if (a[min] > a[j]) {
                    min = j;
                }
            }
            SortUtil.swap(a, i, min);
            // 根据最小值位置交换，定位最终max的位置
            int realMax = n - 1 - i;
            if (n - 1 - i == i) {
                realMax = min;
            }
            if (max == i) {
                max = min;
            }
            SortUtil.swap(a, realMax, max);
        }
    }


}
